MERGE SORT

How do I split a linked list into 2 halves? (Used for merge sort)

• Do a count of the entire linked list, divide by 2, etc. (LESS EFFICIENT)
• Make a pointer move twice as fast as the other

MERGE SORT PSEUDOCODE

• Split the collection into 2 halves.
• Merge sort each half.
• Merge the 2 halves and maintain the sortedness.

3 cases of sorting

• Empty list (just return)
• Just 1 node (just return)
• Normal list